
/***********************************************************************
 * List<A> class
 * 
 * Implementation of immutable lists
 *
 * Signature:
 *  public static <A> List<A> empty ();
 *  public static <A> List<A> cons (A v, List<A> l);
 *  public boolean isEmpty ();
 *  public A first ();
 *  public List<A> rest ();
 *  public String toString ();
 *  public FuncIterator<A> getFuncIterator ();
 *  public Iterator<A> iterator () {
 ***********************************************************************/

import java.util.Iterator;
import java.lang.Iterable;

public abstract class List<A> implements Iterable<A> {

    public static <A> List<A> empty () {
	return new EmptyList<A>();
    }

    public static <A> List<A> cons (A v, List<A> l) {
	return new ConsList<A>(v,l);
    }

    public abstract boolean isEmpty ();
    public abstract A first ();
    public abstract List<A> rest ();
    public abstract String toString ();

    public abstract FuncIterator<A> getFuncIterator ();

    public Iterator<A> iterator () {
	return IteratorAdapter.create(this.getFuncIterator());
    }

}



class EmptyList<A> extends List<A> {

    public EmptyList () {}

    public boolean isEmpty () {
	return true;
    }

    public A first () {
	throw new RuntimeException("EmptyList.first()");
    }

    public List<A> rest () {
	throw new RuntimeException("EmptyList.rest()");
    }

    public String toString () {
	return "";
    }

    public FuncIterator<A> getFuncIterator () {
	return new EmptyFuncIterator<A>();
    }
}



class EmptyFuncIterator<A> implements FuncIterator<A> {

    public EmptyFuncIterator () {}

    public boolean hasElement () {
	return false;
    }

    public A current () {
	throw new java.util.NoSuchElementException("EmptyFuncIterator.current()");
    }

    public FuncIterator<A> advance () {
	throw new java.util.NoSuchElementException("EmptyFuncIterator.advance()");
    }
}



class ConsList<A> extends List<A> {

    private A first;
    private List<A> rest;

    public ConsList (A f, List<A> r) {
	this.first = f;
	this.rest = r;
    }

    public boolean isEmpty () {
	return false;
    }

    public A first () {
	return this.first;
    }

    public List<A> rest () {
	return this.rest;
    }

    public String toString () {
	return this.first() + " " + this.rest();
    }

    public FuncIterator<A> getFuncIterator () {
	return new ConsFuncIterator<A>(this.first(),
				       this.rest().getFuncIterator());
    }
}



class ConsFuncIterator<A> implements FuncIterator<A> {

    private A current;
    private FuncIterator<A> rest;

    public ConsFuncIterator (A c, FuncIterator<A> r) {
	this.current = c;
	this.rest = r;
    }

    public boolean hasElement () {
	return true;
    }

    public A current () {
	return this.current;
    }

    public FuncIterator<A> advance () {
	return this.rest;
    }
}
